package top.likeqc.leetcode.editor.cn;

/** 链接: https://leetcode.cn/problems/largest-sum-of-averages */
public class LargestSumOfAverages {
    public static void main(String[] args) {
        Solution solution = new LargestSumOfAverages().new Solution();
        System.out.println(solution.largestSumOfAverages(new int[] {1, 2, 3, 4, 5, 6, 7}, 4));
    }
    // leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public double largestSumOfAverages(int[] nums, int k) {

            int n = nums.length;
            double[] prefix = new double[n + 1];
            // dp[i][j] 表示 nums[0, i-1] 划分为 j 个子数组时的最大平均和
            double[][] dp = new double[n + 1][k + 1];

            // 计算前缀和
            for (int i = 0; i < n; i++) {
                prefix[i + 1] = prefix[i] + nums[i];
            }
            // 初始化（划分为一个子数组）
            for (int i = 1; i <= n; i++) {
                dp[i][1] = prefix[i] / i;
            }

            for (int j = 2; j <= k; j++) {
                for (int i = j; i <= n; i++) {
                    // 遍历增加一个子组数的划分方式，取最大值
                    for (int x = j - 1; x < i; x++) {
                        dp[i][j] =
                                Math.max(
                                        dp[i][j], dp[x][j - 1] + (prefix[i] - prefix[x]) / (i - x));
                    }
                }
            }

            return dp[n][k];
        }
    }
    // leetcode submit region end(Prohibit modification and deletion)

}
